package java学习.leetcode.editor.cn.数组;
/**
 * @author 刘世锦
 * 2022-09-22 21:45:58	 当前时间
 */
//给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否
//则返回 -1。 
//
// 
//示例 1: 
//
// 输入: nums = [-1,0,3,5,9,12], target = 9
//输出: 4
//解释: 9 出现在 nums 中并且下标为 4
// 
//
// 示例 2: 
//
// 输入: nums = [-1,0,3,5,9,12], target = 2
//输出: -1
//解释: 2 不存在 nums 中因此返回 -1
// 
//
// 
//
// 提示： 
//
// 
// 你可以假设 nums 中的所有元素是不重复的。 
// n 将在 [1, 10000]之间。 
// nums 的每个元素都将在 [-9999, 9999]之间。 
// 
// Related Topics 数组 二分查找 
// 👍 992 👎 0

public class 二分查找{
	public static void main(String[] args) {
		Solution solution = new 二分查找().new Solution();
		int[]nums = {-1,0,3,5,9,12};
		int target = 2;
		System.out.println(solution.search(nums,target));
		
	}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
//		注意事项： 注意数组的i、j是左闭右闭；还是左闭右开
//	左闭右闭
    public int search(int[] nums, int target) {
		int i = 0;
		int j = nums.length-1;
    	while (i<=j){
//			int mid = (i+j)/2;
			int mid = i+((j-i)>>1);
			if (target==nums[mid]){
    			return mid;
			}else if (target>nums[mid]){
    			i = mid+1; //去右区间搜索 [mid+1,right]
			}else if (target<nums[mid]){
    			j = mid-1; //去左区间搜索 [left,mid-1]
			}
		}
    	return -1;
    }
//左闭右开
	public int search1(int[] nums, int target) {
		int left = 0, right = nums.length;
		while (left < right) {
			int mid = left + ((right - left) >> 1);
			if (nums[mid] == target)
				return mid;
			else if (nums[mid] < target)
				left = mid + 1; //去右区间搜索 [mid+1,right)
			else if (nums[mid] > target)
				right = mid;   //去左区间搜索 [left,mid)
		}
		return -1;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
